#include<iostream>
#include<vector>
#include<string.h>
using namespace std;

//完全背包模板
const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];

void test1(){
    //输入物品个数和背包体积
    cin >> n >> V;

    //输入每个物品的体积和价值
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }

    //问题一状态表示 dp[i][j]表示挑选前i个物品，背包体积不超过j的所有选法中，最大的价值
    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= V; j++){
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]){
                dp[i][j] = max(dp[i][j - v[i]] + w[i], dp[i][j]);
            }
        }
    }
    //输出结果
    cout << dp[n][V] << endl;

    //初始化状态表
    memset(dp, 0, sizeof dp);

    //问题二状态表示 dp[i][j]表示挑选前i个物品，背包体积恰好等于j的所有选法中，最大的价值
    //先初始化第一行为-1，表示不存在的情况
    for (int j = 1; j <= V; j++){
        dp[0][j] = -1;
    }
    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= V; j++){
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i][j - v[i]] != -1){
                dp[i][j] = max(dp[i][j - v[i]] + w[i], dp[i][j]);
            }
        }
    }
    //输出结果
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}
//空间优化
int dp[N];
void test2(){
    //输入物品个数和背包体积
    cin >> n >> V;

    //输入每个物品的体积和价值
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }

    //问题一状态表示 dp[i][j]表示挑选前i个物品，背包体积不超过j的所有选法中，最大的价值
    //填表
    for (int i = 1; i <= n; i++){
        //和01背包不同的是从左往右填
        for (int j = v[i]; j <= V; j++){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    //输出结果
    cout << dp[V] << endl;

    //初始化状态表
    memset(dp, 0, sizeof dp);

    //问题二状态表示 dp[i][j]表示挑选前i个物品，背包体积恰好等于j的所有选法中，最大的价值
    //先初始化第一行为-1，表示不存在的情况
    for (int j = 1; j <= V; j++){
        dp[j] = -1;
    }
    //填表
    for (int i = 1; i <= n; i++){
        for (int j = v[i]; j <= V; j++){
            if (dp[j - v[i]] != -1){
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }
    //输出结果
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
}

//322.零钱兑换
const int INF = 0x3f3f3f3f;
int coinChange(vector<int>& coins, int amount){
    int n = coins.size();

    //状态表示 dp[i][j]表示从前i个硬币中挑选，总和恰好等于j，所有的选法中最少的硬币个数
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
    //初始化第一行为-1，表示不存在的情况
    for (int j = 1; j <= amount; j++){
        dp[0][j] = INF;
    }

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= amount; j++){
            dp[i][j] = dp[i - 1][j];
            if (j >= coins[i-1]){
                dp[i][j] = min(dp[i][j - coins[i-1]] + 1, dp[i][j]);
            }
        }
    }

    //返回值
    return dp[n][amount] >= INF ? -1 : dp[n][amount];
}
//空间优化
int coinChange(vector<int>& coins, int amount){
    int n = coins.size();

    //状态表示
    vector<int> dp(amount + 1);

    //初始化
    for (int j = 1; j <= amount; j++){
        dp[j] = INF;
    }

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = coins[i - 1]; j <= amount; j++){
            dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
        }
    }

    //返回值
    return dp[amount] == INF ? -1 : dp[amount];
}

//518.零钱兑换2
int change(int amount, vector<int>& coins){
    int n = coins.size();

    //状态表示 dp[i][j]表示挑选前i个硬币，总和恰好为j的选法总数
    vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(amount + 1));
    //初始化
    dp[0][0] = 1;

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= amount; j++){
            dp[i][j] = dp[i - 1][j];
            if (j >= coins[i - 1]){
                dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
    }

    //返回值
    return dp[n][amount];
}
//空间优化
int change(int amount, vector<int>& coins){
    int n = coins.size();

    //状态表示
    vector<unsigned long long> dp(amount + 1);
    //初始化
    dp[0] = 1;

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = coins[i-1]; j <= amount; j++){
            dp[j] = dp[j] + dp[j - coins[i - 1]];
        }
    }

    //返回值
    return dp[amount];
}

//完全平方数
int numSquares(int n){
    int m = sqrt(n);

    //状态表示 dp[i][j]表示从前i个数中挑选，平方总和恰好等于j的所有选法中，使用数字最小的个数
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    //初始化
    for (int j = 1; j <= n; j++){
        dp[0][j] = INF;
    }

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 0; j <= n; j++){
            dp[i][j] = dp[i - 1][j];
            if(j>=i*i){
                dp[i][j] = min(dp[i][j - i * i] + 1, dp[i][j]);
            }
        }
    }

    //返回值
    return dp[m][n] == INF ? 0 : dp[m][n];
}
//空间优化
int numSquares(int n){
    int m = sqrt(n);

    //状态表示
    vector<int> dp(n + 1);
    //初始化
    for (int j = 1; j <= n; j++){
        dp[j] = INF;
    }

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = i * i; j <= n; j++){
            dp[j] = min(dp[j], dp[j - i * i] + 1);
        }
    }

    //返回值
    return dp[n] == INF ? 0 : dp[n];
}

int main(){

    return 0;
}